package hot100.logos31To40;

import hot100.datastruct.ListNode;

/**
 * @author logos
 * date 2025/7/13 11:49
 * @version v1.0
 * @Package hot100.logos31To40
 */
public class logos33 {

    /**
     * 33.排序链表
     * https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public static ListNode start, end;

        public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
            ListNode pre;
            if (l1.val <= l2.val) {
                pre = l1;
                start = l1;
                l1 = l1.next;
            } else {
                pre = l2;
                start = l2;
                l2 = l2.next;
            }
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    pre.next = l1;
                    pre = l1;
                    l1 = l1.next;
                } else {
                    pre.next = l2;
                    pre = l2;
                    l2 = l2.next;
                }
            }
            if (l1 != null) {
                pre.next = l1;
                end = r1;
            } else {
                pre.next = l2;
                end = r2;
            }
        }

        public static ListNode findNode(ListNode start, int k) {
            while (start.next != null && --k > 0) {
                start = start.next;
            }
            return start;
        }

        public ListNode sortList(ListNode head) {
            int n = 0;
            ListNode cur = head;
            while (cur != null) {
                n++;
                cur = cur.next;
            }
            ListNode l1, r1, l2, r2, next, lastEnd;
            for (int step = 1; step < n; step <<= 1) {
                l1 = head;
                r1 = findNode(l1, step);
                l2 = r1.next;
                r2 = findNode(l2, step);
                next = r2.next;
                r1.next = null;
                r2.next = null;
                merge(l1, r1, l2, r2);
                head = start;
                lastEnd = end;
                while (next != null) {
                    l1 = next;
                    r1 = findNode(l1, step);
                    l2 = r1.next;
                    if (l2 == null) {
                        lastEnd.next = l1;
                        break;
                    }
                    r2 = findNode(l2, step);
                    next = r2.next;
                    r1.next = null;
                    r2.next = null;
                    merge(l1, r1, l2, r2);
                    lastEnd.next = start;
                    lastEnd = end;
                }
            }
            return head;
        }
    }

    class Solution2 {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode head2 = midNode(head);
            // 分治
            head = sortList(head);
            head2 = sortList(head2);
            // 合并
            return mergeTwoLists(head, head2);
        }

        // 876. 链表的中间结点（快慢指针）
        private ListNode midNode(ListNode head) {
            ListNode pre = head;
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                pre = slow; // 记录 slow 的前一个节点
                slow = slow.next;
                fast = fast.next.next;
            }
            pre.next = null; // 断开 slow 的前一个节点和 slow 的连接
            return slow;
        }

        // 21. 合并两个有序链表（双指针）
        private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
            ListNode cur = dummy;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    cur.next = list1;
                    list1 = list1.next;
                } else {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
            return dummy.next;
        }
    }

}
